package codingforgreat.class48;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Lc472 {
    public static class TreeNode{
        TreeNode[] path;
        boolean end;
        public TreeNode(){
            end = false;
            path = new TreeNode[26];
        }
    }
    public static List<String> findAllConcatenatedWordsInADict(String[] words) {
        TreeNode root = new TreeNode();
        ArrayList<String> ans = new ArrayList<>();
        if(words.length < 3){
            return ans;
        }
        Arrays.sort(words,(a, b)->{
            return a.length() - b.length();
        });
        for(int i = 0; i < words.length;i++){
            char[] str = words[i].toCharArray();
            if(str.length > 0 && spilt(str,root,0)){
                ans.add(words[i]);
            }else{
                insert(root,str);
            }
        }
        return ans;
    }
    public static boolean spilt(char[] str,TreeNode root,int index){
        boolean ans = false;
        if(index == str.length){
            ans = true;
        }else{
            TreeNode node = root;
            for(int i = index;i < str.length;i++){
                int path = str[i] - 'a';
                if(node.path[path] == null){
                    break;
                }
                node = node.path[path];
                if (node.end && spilt(str, root, i + 1)) {
                    ans = true;
                    break;
                }
            }
        }
        return ans;
    }
    public static void insert(TreeNode root,char[] str){
        TreeNode node = root;
        for(int i = 0;i < str.length;i++){
            if(node.path[str[i] - 'a'] == null){
                node.path[str[i] - 'a'] = new TreeNode();
            }
            node = node.path[str[i] - 'a'];
        }
        node.end = true;
    }

    public static void main(String[] args) {
        String[] strs = new String[]{"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
        findAllConcatenatedWordsInADict(strs);

    }
}
